package com.tried.kind.algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertionSort {


    /**
     *  1、基本思想
     *    直接插入排序的基本思想是：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，
     *    则交换，直到全部元素都比较过为止。
     *
     *   2、算法描述
     * 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
     *
     * ①. 从第一个元素开始，该元素可以认为已经被排序
     * ②. 取出下一个元素，在已经排序的元素序列中从后向前扫描
     * ③. 如果该元素（已排序）大于新元素，将该元素移到下一位置
     * ④. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
     * ⑤. 将新元素插入到该位置后
     * ⑥. 重复步骤②~⑤
     *
     * 直接插入排序复杂度如下：
     *
     * 最好情况下，排序前对象已经按照要求的有序。比较次数(KCN)：n−1；移动次数(RMN)为0。则对应的时间复杂度为O(n)。
     * 最坏情况下，排序前对象为要求的顺序的反序。第i趟时第i个对象必须与前面i个对象都做排序码比较，
     * 并且每做1次比较就要做1次数据移动（从上面给出的代码中看出）。比较次数(KCN)：n²/2 ; 移动次数(RMN)为：n²/2。则对应的时间复杂度为O(n²)。
     * 如果排序记录是随机的，那么根据概率相同的原则，在平均情况下的排序码比较次数和对象移动次数约为n²/2，因此，直接插入排序的平均时间复杂度为O(n²)。
     * 平均时间复杂度	最好情况    	最坏情况	    空间复杂度
     * O(n²)	        O(n)	        O(n²)	O(1)
     * Tips: 由于直接插入排序每次只移动一个元素的位， 并不会改变值相同的元素之间的排序， 因此它是一种稳定排序。
     *
     * 可优化：如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。可以认为是插入排序的一个变种，称为二分查找插入排序。
     * @param args
     */
    public static void main(String[] args) {
        int[] arry = {5,9,3,4,79,46,89,26,75,8,7,1,55,234,567,234,67,78,34,32};
        for (int i = 1; i < arry.length; i++){
            int temp = arry[i];
            for (int j = i; j >=0; j--){
                if(j >0 && temp < arry[j-1]){   // 升序
                    arry[j] = arry[j-1];
                    System.out.println("排序："+Arrays.toString(arry));
                } else{
                    arry[j] = temp;
                    System.out.println("排序："+Arrays.toString(arry));
                    break;
                }
            }
        }
    }
}
